﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _9.MaximalElementInPortion
{
    class MaximalElementInPortion
    {
        static void Main(string[] args)
        {
            List<int> array = new List<int> { 3, 2, 3, 9, 6, 1, 4, 7, 20, 15, 6, 8, 4, 2, 2, 4 };
            int[] sortedArray = new int[array.Count];
            int index = 0;

            while (array.Count != 0)
            {
                int[] candidate =FindLargestAtPosition(array,0,array.Count);
                sortedArray[index] = candidate[0];
                array.RemoveAt(candidate[1]);
                index++;
            }

            Print(sortedArray);
        }

        private static int[] FindLargestAtPosition(List<int> array,int start, int end)
        {
            int candidateSmallestNumber;
            int candidateSmallestNumberPosition;
            candidateSmallestNumber = array[0];
            candidateSmallestNumberPosition = 0;

            for (int i = start; i < end; i++)
            {
                if (candidateSmallestNumber >= array[i])
                {
                    candidateSmallestNumber = array[i];
                    candidateSmallestNumberPosition = i;
                }
            }
            int[] candidate = { candidateSmallestNumber, candidateSmallestNumberPosition };
            return candidate;                 
        }

        private static void Print(int[] sortedArray)
        {
            Console.Write("The array sorted is: " + sortedArray[0]);
            for (int i = 1; i < sortedArray.Length; i++)
            {
                Console.Write(", " + sortedArray[i]);
            }
            Console.WriteLine();
        }


    }
}